/**
 * [152] 乘积最大子数组
 *
 * @format
 * @lc app=leetcode.cn id=152 lang=javascript
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
// 动态规划
// fmax(i) 表示第 i 个元素结尾的最大积
// # fmax(i) = max{nums[i], fmax(i-1)*nums[i], fmin(i-1)*nums[i]}
// fmin(i) 表示第 i 个元素结尾的最小积，尽量小，期待负负得正
// # fmin(i) = min{nums[i], fmin(i-1)*nums[i], fmax(i-1)*nums[i]}
// max(i) 包括以第 i 个元素结尾的历史最大积
// # max(i) = max{max(i-1), fmax(i)}
var maxProduct = function (nums) {
    let [max, fmax, fmin] = [nums[0], nums[0], nums[0]]
    for (let i = 1; i < nums.length; i++) {
        let temp = fmax
        fmax = Math.max(nums[i], fmax * nums[i], fmin * nums[i])
        fmin = Math.min(nums[i], fmin * nums[i], temp * nums[i])
        max = Math.max(fmax, max)
    }
    return max
}
// @lc code=end
